package com.str.tree;
public class UFTree {      // General tree for UNION/FIND

  private int[] array;          // Node array

  public UFTree(int size) {     // Constructor
    array = new int[size]; // Create node array
    for (int i = 0; i < size; i++)
      array[i] = -1;
  }
  
  public boolean differ(int a, int b) {
  	int root1 = find(a);
  	int root2 = find(b);
  	if (root1 != root2) {
  	  union(root1, root2);
  	  return true;
  	}
  	else return false;
  }

  /*private void union(int root1, int root2) {  // Merge two subtrees
    array[root2] = root1;        // Merge subtrees
  }*/
  
  private void union(int root1, int root2) {  // Merge two subtrees
    if (array[root1] <= array[root2]) {
      array[root1] += array[root2];	
      array[root2] = root1;          
    }
    else {
      array[root2] += array[root1];    	
      array[root1] = root2;
    }
  }
  
  /*private void union(int root1, int root2) {  // Merge two subtrees
    if (array[root1] <= array[root2]) {
      if (array[root1] == array[root2])
        array[root1]--;    	
      array[root2] = root1;
    }            
    else array[root1] = root2;
  }*/
  
  private int find(int curr) {   // Find root
    while (array[curr] >= 0) 
      curr = array[curr];
    return curr;            // At root
  }
  
  /*private int find(int curr) {       // With path compression  
    if (array[curr] < 0) return curr;  // At root
    return array[curr] = find(array[curr]);
  }*/
  
  public void print() {
    for (int i = 0; i < array.length; i++) {
      int curr = i;	
      while (curr >= 0) {
        System.out.print((char) (curr + 'A')); 	
        curr = array[curr];
        if (curr >= 0) System.out.print(" -> ");
      } 
      System.out.println();
    }
    System.out.println();
  }
}
